package sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
       //第一个
       int[] arr = new int[5000000];
        Random r = new Random(47);
        for (int i = 0; i < 5000000; i++) {
            arr[i]=r.nextInt();
        }
        long l = System.currentTimeMillis();
        sort1(arr, 0, arr.length - 1);
        long l2 = System.currentTimeMillis();
        System.out.println("第一次="+(l2-l));
         //第二个
        for (int i = 0; i < 5000000; i++) {
            arr[i]=r.nextInt();
        }
        l = System.currentTimeMillis();
        sort2(arr, 0, arr.length - 1);
        l2 = System.currentTimeMillis();
        System.out.println("第二次="+(l2-l));
        for (int i = 0; i < 5000000; i++) {
            arr[i]=r.nextInt();
        }
        l = System.currentTimeMillis();
        sort3(arr, 0, arr.length - 1);
        l2 = System.currentTimeMillis();
        System.out.println("第三次="+(l2-l));
       /* int[] arr = new int[]{1,7,4,3,5,1,10,8,40,70};
        sort3(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));*/

    }
    public static void sort2(int[] arr,int left,int rigth){
        if(left>rigth){
        return;}
        int i=left;
        int j=rigth;
        int base=arr[left];
        int temp=0;
        while(i!=j){
            while(arr[j]>=base&&i<j){
                j--;
            }
            while(arr[i]<=base&&i<j){
                i++;
            }
            temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
        arr[left]=arr[i];
        arr[i]=base;
        sort2(arr,left,j-1);
        sort2(arr,j+1,rigth);
    }
    private static void sort1(int[] arr, int left, int right) {
         int l = left;
         int r =right;
         int pivot=arr[(left + right)/2];
         int temp=0;
         while(l<r){

             while (arr[l]<pivot){
                 l++;
             }
             while (arr[r]>pivot){
                 r--;
             }
             if(l>=r)
                 break;
             temp=arr[l];
             arr[l]=arr[r];
             arr[r]=temp;
             if(arr[l]==pivot)
                 r--;
             if(arr[r]==pivot)
                 l++;
         }
         if(r==l){
             l++;
         r--;}
         if(left<r){
             sort1(arr,left,r);
         }
         if(right>l){
             sort1(arr,l,right);
         }

    }
    private static void sort3(int[] arr, int start, int end) {
            if(start>=end){
            return;
        }
        int i = start;
        int j=end;
        int index=arr[i];
        while(i<j){
            while(i<j&&arr[j]>=index){
                j--;
            }if(arr[j]<index){
                arr[i]=arr[j];
            }
            while(i<j&&arr[i]<index){
                i++;
            }if(arr[i]>index){
                arr[j]=arr[i];
            }
        }
        arr[j]=index;
        sort3(arr,start,i);
        sort3(arr,i+1,end);}
}